#include<iostream>
#include<vector>
#include<algorithm>


using std::cout;
using std::vector;
using std::swap;


void heapify(vector<int>& vec,int size ,int tag)
{
    int max =tag;
    int left =2* tag+1;
    int right =2* tag+2;
    if(left<size&&vec[tag]<vec[left])
    {
        tag = left;
    }
    if(right<size&&vec[tag]<vec[right])
    {
        tag=right;
    }
    if(tag!=max)
    {
        swap(vec[tag],vec[max]);
        heapify(vec,size,tag);
    }

}

void make_heap(vector<int>& vec,int size)
{
    int idx =(size-2)/2;
    for(idx;idx>=0;--idx)
    {
        heapify(vec,size,idx);
    }
}

void heap_sort(vector<int>& vec)
{
    make_heap(vec,vec.size());
    //创建堆
    //
    for(int i =0;i<vec.size();++i)
    {
        swap(vec[0],vec[vec.size()-i-1]);
        heapify(vec,vec.size()-i-1,0);
    }


}

int main()
{
    vector<int> vec = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    heap_sort(vec);
    for(const auto&i:vec)
    {
        cout<<i<<"\n";
    }
    
}
